Tree Recursion Patterns

Table of Contents

1. Basic Tree Structure
2. Fundamental Recursion Patterns
3. Top-Down Recursion
4. Bottom-Up Recursion
5. Divide and Conquer
6. Backtracking in Trees
7. Common Problem Types
8. Time & Space Complexity

Basic Tree Structure

// Binary Tree Node
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// N-ary Tree Node
class NaryNode {
    constructor(val, children = []) {
        this.val = val;
        this.children = children;
    }
}

Fundamental Recursion Patterns

1. Basic Traversal Template

function traverse(root) {
    // Base case
    if (!root) return;

    // Process current node (preorder)
    console.log(root.val);

    // Recursive calls
    traverse(root.left);
    traverse(root.right);

    // Process current node (postorder)
    // console.log(root.val);
}

2. Value Returning Template

function processTree(root) {
    // Base case
    if (!root) return null; // or appropriate default value

    // Get results from children
    const leftResult = processTree(root.left);
    const rightResult = processTree(root.right);

    // Combine results with current node
    return combineResults(root.val, leftResult, rightResult);
}

Top-Down Recursion

Pattern: Pass information down from parent to children. Good for path-based problems.

Example: Maximum Depth

function maxDepth(root) {
    function dfs(node, depth) {
        if (!node) return depth;

        const leftDepth = dfs(node.left, depth + 1);
        const rightDepth = dfs(node.right, depth + 1);

        return Math.max(leftDepth, rightDepth);
    }

    return dfs(root, 0);
}

Example: Path Sum

function hasPathSum(root, targetSum) {
    function dfs(node, currentSum) {
        if (!node) return false;

        currentSum += node.val;

        // Leaf node check
        if (!node.left && !node.right) {
            return currentSum === targetSum;
        }

        return dfs(node.left, currentSum) || dfs(node.right, currentSum);
    }

    return dfs(root, 0);
}

Example: Root to Leaf Paths

function binaryTreePaths(root) {
    const result = [];

    function dfs(node, path) {
        if (!node) return;

        path.push(node.val);

        // Leaf node
        if (!node.left && !node.right) {
            result.push(path.join('->'));
        } else {
            dfs(node.left, [...path]); // Create new array
            dfs(node.right, [...path]);
        }
    }

    dfs(root, []);
    return result;
}

Bottom-Up Recursion

Pattern: Gather information from children and bubble up. Good for tree property problems.

Example: Maximum Depth (Bottom-Up)

function maxDepth(root) {
    if (!root) return 0;

    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);

    return Math.max(leftDepth, rightDepth) + 1;
}

Example: Diameter of Binary Tree

function diameterOfBinaryTree(root) {
    let maxDiameter = 0;

    function height(node) {
        if (!node) return 0;

        const leftHeight = height(node.left);
        const rightHeight = height(node.right);

        // Update diameter at current node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        return Math.max(leftHeight, rightHeight) + 1;
    }

    height(root);
    return maxDiameter;
}

Example: Balanced Binary Tree

function isBalanced(root) {
    function checkBalance(node) {
        if (!node) return { balanced: true, height: 0 };

        const left = checkBalance(node.left);
        const right = checkBalance(node.right);

        const balanced = left.balanced &&
                        right.balanced &&
                        Math.abs(left.height - right.height) <= 1;

        return {
            balanced,
            height: Math.max(left.height, right.height) + 1
        };
    }

    return checkBalance(root).balanced;
}

Divide and Conquer

Pattern: Split problem into subproblems, solve independently, then combine.

Example: Merge Two Binary Trees

function mergeTrees(root1, root2) {
    // Base cases
    if (!root1) return root2;
    if (!root2) return root1;

    // Combine current nodes
    root1.val += root2.val;

    // Recursively merge subtrees
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);

    return root1;
}

Example: Lowest Common Ancestor

function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    // If both sides return non-null, current node is LCA
    if (left && right) return root;

    // Return whichever side found a target
    return left || right;
}

Backtracking in Trees

Pattern: Explore paths and undo choices. Good for finding all solutions.

Example: All Root-to-Leaf Paths with Sum

function pathSumII(root, targetSum) {
    const result = [];

    function backtrack(node, path, currentSum) {
        if (!node) return;

        // Add current node to path
        path.push(node.val);
        currentSum += node.val;

        // Check if we found a valid path
        if (!node.left && !node.right && currentSum === targetSum) {
            result.push([...path]); // Create copy
        }

        // Explore children
        backtrack(node.left, path, currentSum);
        backtrack(node.right, path, currentSum);

        // Backtrack: remove current node
        path.pop();
    }

    backtrack(root, [], 0);
    return result;
}

Example: Binary Tree Maximum Path Sum

function maxPathSum(root) {
    let maxSum = -Infinity;

    function maxGain(node) {
        if (!node) return 0;

        // Get maximum gain from left and right subtrees
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);

        // Current path sum including this node as highest point
        const currentMax = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentMax);

        // Return max gain if we continue path through this node
        return node.val + Math.max(leftGain, rightGain);
    }

    maxGain(root);
    return maxSum;
}

Common Problem Types

1. Tree Validation

function isValidBST(root) {
    function validate(node, min, max) {
        if (!node) return true;

        if (node.val <= min || node.val >= max) return false;

        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }

    return validate(root, -Infinity, Infinity);
}

2. Tree Construction

function buildTree(preorder, inorder) {
    if (!preorder.length || !inorder.length) return null;

    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);

    const rootIndex = inorder.indexOf(rootVal);

    root.left = buildTree(
        preorder.slice(1, rootIndex + 1),
        inorder.slice(0, rootIndex)
    );

    root.right = buildTree(
        preorder.slice(rootIndex + 1),
        inorder.slice(rootIndex + 1)
    );

    return root;
}

3. Tree Serialization

function serialize(root) {
    const result = [];

    function preorder(node) {
        if (!node) {
            result.push('null');
            return;
        }

        result.push(node.val.toString());
        preorder(node.left);
        preorder(node.right);
    }

    preorder(root);
    return result.join(',');
}

function deserialize(data) {
    const values = data.split(',');
    let index = 0;

    function buildTree() {
        if (values[index] === 'null') {
            index++;
            return null;
        }

        const node = new TreeNode(parseInt(values[index]));
        index++;

        node.left = buildTree();
        node.right = buildTree();

        return node;
    }

    return buildTree();
}

Time & Space Complexity

Common Patterns:

Time Complexity:

• Simple Traversal: O(n) - visit each node once
• Path Finding: O(n) - might visit all nodes
• Tree Construction: O(n) - process each element once
• Validation: O(n) - check all nodes

Space Complexity:

• Recursive Stack: O(h) where h is tree height
  • Balanced tree: O(log n)
  • Skewed tree: O(n)
• Result Storage: Depends on problem (paths, values, etc.)

Optimization Tips:

1. Early Termination: Return immediately when answer is found
2. Memoization: Cache results for overlapping subproblems
3. Iterative Alternatives: Use stack/queue to avoid recursion stack
4. In-place Modifications: Modify existing tree instead of creating new one

// Example: Early termination in search
function findTarget(root, target) {
    if (!root) return false;
    if (root.val === target) return true; // Found it!

    return findTarget(root.left, target) || findTarget(root.right, target);
}

// Example: Iterative traversal to save space
function maxDepthIterative(root) {
    if (!root) return 0;

    const stack = [[root, 1]];
    let maxDepth = 0;

    while (stack.length) {
        const [node, depth] = stack.pop();
        maxDepth = Math.max(maxDepth, depth);

        if (node.left) stack.push([node.left, depth + 1]);
        if (node.right) stack.push([node.right, depth + 1]);
    }

    return maxDepth;
}

Key Takeaways

1. Identify the pattern: Top-down vs Bottom-up vs Divide & Conquer
2. Define base cases: What happens with null nodes?
3. Recursive relation: How do you combine results from children?
4. State management: What information needs to be passed down or up?
5. Optimization: Can you terminate early or avoid redundant work?

Remember: Most tree problems follow these fundamental patterns. Master these templates and you can solve a wide variety of tree-related challenges!